package offerbook;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created at 2019/10/26 0026 下午 8:55
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
 * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
 * <p>
 * 方式1：时间O(n*logn)，空间O(1)
 * 对数组进行排序,数组长为length,则length/2位置(奇数个是中间，偶数个是后一个)的数必定是符合要求的数(如果有)。
 * 也就是中位数必定是目标数字(如果有)
 * <p>
 * 方式2：时空都是O(n)
 * 遍历数组，利用hashMap记录个数，当个数大于等于(length/2+1),如9那就是大于等于5,10就是大于等于6 退出
 * <p>
 * 方式3：基于快排的思想，Partition的过程其实就是找下标范围。
 * 找中位数其实就是找第n/2小的数,可以通过partition找到第n/2小的数的范围。
 * 找topK问题就可以延伸出若干种算法了，见{@link Code30_TopK}
 * <p>
 * 时间O(n),空间：如果不允许改变原数组则需要拷贝一份是O(n)，允许改变则O(1)
 * <p>
 * TODO【理解】方式4：基于数组性质，复杂度同方式3，但是不会改变原数组内容，最佳解决方法
 * <p>
 * 方式5：分治，统计左右众数，合并再统计
 */
public class Code29_FindMoreThanHalfNumInArray {

    //方式1：排序：通过测试
    public static int getHalf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        Arrays.sort(nums);
        int count = 1;
        //
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //
            if (nums[i] == nums[i - 1]) {
                if (++count > nums.length / 2) return nums[i];
            } else {
                res = nums[i];
                count = 1;
            }
        }
        return res;
    }

    //方式2：利用HashMap 通过测试
    public static int getHalf1(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer num : nums) {
            if (map.containsKey(num)) {
                if (map.get(num) + 1 >= nums.length / 2) return num;
                map.put(num, map.get(num) + 1);
            } else
                map.put(num, 1);
        }
        /*for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() > nums.length/2) return entry.getKey();
        }*/
        //个数不超过一半的情况
        return -1;
    }


    /**
     * 方式3：通过测试，时间O(n)，空间O(1)但是破坏了原数组顺序
     * 也可以通过另外拷贝一份数组 ，空间是O(n)
     * <p>
     * 通过NetherFlag的partition找到第n/2小的数的索引范围
     * <p>
     * 递归版本见{@link Code30_TopK#}
     */
    public static int getHalf2(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        if (array.length == 1) {
            return array[0];
        }
        //第n/2+1小的数,这里用 leetcode.array.length >> 1+1 也可以
        int midIndex = array.length >> 1;
        int begin = 0;
        int end = array.length - 1;

        //找到第n/2+1小的数在数组中索引的范围
        int[] range = partition(array, begin, end);
        while (midIndex < range[0] || midIndex > range[1]) {
            if (midIndex < range[0]) {
                end = range[0] - 1;
            } else {
                begin = range[1] + 1;
            }
            range = partition(array, begin, end);
        }
        //在length/2处必定是目标,奇数是中间，偶数是后一个(前一个也行)，
        //统计目标个数是否大于等于length/2+1
        return range[1] - range[0] >= array.length / 2 ? array[midIndex] : 0;

    }

    private static int[] partition(int[] arr, int begin, int end) {
        int target = arr[(int) (begin + Math.random() * (end - begin + 1))];
        int less = begin - 1;
        int cur = begin;
        int more = end + 1;
        while (cur != more) {
            if (arr[cur] < target) {
                swap(arr, ++less, cur++);
            } else if (arr[cur] > target) {
                swap(arr, cur, --more);
            } else {
                cur++;
            }
        }
        return new int[]{less + 1, more - 1};
    }


    public static void swap(int[] arr, int index1, int index2) {
        int tmp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = tmp;
    }


    /**
     * 方式4：时间O(N) 空间O(1)  并且不改变原数组状态
     * <p>
     * 如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。
     * <p>
     * 在遍历数组时保存两个值：一是数组中一个数字，一是次数。
     * <p>
     * 遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；
     * <p>
     * 若次数为0，则保存下一个数字，并将次数置为1。
     * <p>
     * 遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。
     * <p>
     * 如果这两个不同的数 都不是 目标数，那么划去对目标没有影响
     * <p>
     * 如果这两个数有目标数，那么目标数和非目标数会抵消，对结果也没影响
     */
    public static int getHalf3(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }

        // 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
        int result = array[0];
        int times = 1; // 次数

        for (int i = 1; i < array.length; i++) {
            if (times == 0) {
                // 更新result的值为当前元素，并置次数为1
                result = array[i];
                times = 1;
            } else if (array[i] == result) {
                times++; // 相同则加1
            } else {
                times--; // 不同则减1
            }
        }

        // 判断result是否符合条件，即出现次数大于数组长度的一半
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == result) {
                if (++count >= array.length / 2 + 1) {
                    return result;
                }
            }
        }
        return 0;
    }

    /**
     * 方式5：分治。如果我们知道数组左边一半和右边一半的众数，我们就可以用线性时间知道全局的众数是哪个。
     * <p>
     * 这里我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。
     * 由于传输子数组需要额外的时间和空间，所以我们实际上只传输子区间的左右指针 lo 和 hi 表示相应区间的左右下标。
     * 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
     * <p>
     * 如果回溯后某区间的长度大于 1 ，我们必须将左右子区间的值合并。
     * 如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
     * 否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。
     * 原问题的答案就是下标为 0 和 n 之间的众数这一子问题
     *
     * @return
     */
    public static int process6(int[] nums, int start, int end) {
        // base case; the only element in an array of size 1 is the majority element.
        if (start == end) {
            return nums[start];
        }

        // recurse on left and right halves of this slice.
        int mid = (end - start) / 2 + start;
        int lnum = process6(nums, start, mid);
        int rnum = process6(nums, mid + 1, end);

        return merge(nums, lnum, rnum, start, end);

    }

    /**
     * 统计谁是众数。 left 和right是待选项
     */
    private static int merge(int[] nums, int lnum, int rnum, int start, int end) {
        // if the two halves agree on the majority element, return it.
        if (lnum == rnum) {
            return lnum;
        }

        // otherwise, count each element and return the "winner".
        int leftCount = countInRange(nums, lnum, start, end);
        int rightCount = countInRange(nums, rnum, start, end);
        return leftCount > rightCount ? lnum : rnum;

    }

    private static int countInRange(int[] nums, int num, int start, int end) {
        int count = 0;
        for (int i = start; i <= end; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

}
